class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    void dfs(vector<int>& candidates,int index,int target)
    {
        if(target == 0)
        {
            //说明此时的path中的路径就是答案
            ret.push_back(path);
            return;
        }
        if(target<0||index == candidates.size())
        {
            return;
        }
        for(int i = index;i<candidates.size();i++)
        {
            if(target - candidates[index]<0)
            {
                break;//不用进行选择了后面的值都是不可能让值等于target的
            }
            path.push_back(candidates[i]);
            dfs(candidates,i,target-candidates[i]);
            path.pop_back();//恢复现场
            // 这里的i从index开始，是因为同一个元素可以进行重复的选择，并且
            // 这样可以完成剪枝，比如 3 4 5元素我第一个元素选择了4，3已经在上一层选择过了而3 4 和4 3是一个重复
            //  的子集，所以在选择4的时候我从4的位置开始进行重新选择
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());//对数组中的元素进行排序,用于之后的剪枝，如果选择到了某一个元素之后
        //此时的和已经大于了target那么也没有必要往下进行寻找了,这就是排序的作用也是为了剪枝
        dfs(candidates,0,target);
        return  ret;
        
    }
};